home *** CD-ROM | disk | FTP | other *** search
/ Czech Logic, Card & Gambling Games / Logické hry.iso / hry / Sokoban / source / think.cpp < prev   
C/C++ Source or Header  |  2005-09-26  |  47KB  |  1,751 lines
  1. #include <windows.h>
  2. #pragma hdrstop
  3. #include <string.h>
  4. #include <assert.h>
  5. #include "level.h"
  6. //---------------------------------------------------------------------------
  7. /*
  8.  
  9. POZOR!
  10.  velikost zßsobnφku nastavte na 256MB (v Project/Settings/Linker/Output)
  11.  velikost swapovacφho souboru nastavte na 1200MB (Ovlßdacφ panely/SystΘm/Up°esnit/Mo₧nosti v²konu)
  12.  
  13.  Pam∞¥
  14. posTable:  (18+Nobj)*maxPos
  15. hashTable: 8*maxPos
  16. movedObj:  Nobj*48*maxPos
  17. */
  18.  
  19. struct Move {
  20.  Psquare obj,next; //odkud kam se p°esouvß
  21.  short dist;       //vzdßlenost mezi hrßΦem a obj
  22.  short direct;     //sm∞r p°esunu
  23. };
  24. typedef Move *PMove;
  25.  
  26. int DXY=1;   //2 pro vφce ne₧ 256 polφ, jinak 1
  27.  
  28. int
  29.  Nobj,     //poΦet objekt∙
  30.  Nstore,   //poΦet ·lo₧iÜ¥
  31.  Nground,  //poΦet polφΦek, kde nenφ ze∩
  32.  posSize,  //dΘlka pozice bez hlaviΦky (v bytech)
  33.  posSize1, //jako posSize, ale sni₧uje se p°i testBlocked
  34.  posSize2, //alokovanß dΘlka na pozici v posTable
  35.  DHDR,     //dΘlka hlaviΦky p°ed pozicφ
  36.  distId,   //ka₧dΘ volßnφ findObjects pou₧ije jinΘ id
  37.  maxPos,   //max. poΦet prohledßvan²ch pozic
  38.  maxPos0=5000000,//omezenφ maxPos
  39.  maxMem=900, //omezenφ adresovΘho prostroru (MB)
  40.  DhashTable, //dΘlka hashovacφ tabulky
  41.  algorithm,  //0=do hloubky, 1=do Üφ°ky, 2=dijkstra, 3=gener
  42.  testing,    //byl zmenÜen poΦet objekt∙ uvnit° testBlocked
  43.  finalDone,  //poΦet objekt∙ na ·lo₧iÜtφch
  44.  *finalDistA;//pole pro vÜechny finalDists
  45.  
  46. Pchar
  47.  *hashTable, //hashovacφ tabulka prohledan²ch pozic
  48.  *hashTablek,//konec hashovacφ tabulky
  49.  UfoundPos,  //nalezenß koncovß pozice
  50.  UfoundPosD, 
  51.  posTable,   //pam∞¥ na vÜechny prohledanΘ pozice
  52.  posTablek,
  53.  UposTable,  //ukazatel na volnΘ mφsto v posTable
  54.  UfoundSol,  //ukazatel na konec °eÜenφ
  55.  firstMove,  //tahy vzniklΘ smazßnφm slep²ch uliΦek
  56.  UfirstMove,
  57.  finalPos;   //koncovß pozice (bez hrßΦe)
  58.  
  59. PMove
  60.  movedObj;   //pam∞¥ pro Move
  61.  
  62. Psquare
  63.  *distBuf1,*distBuf2, //pomocnΘ buffery pro findDist a findObjects
  64.  *i2p,      //p°evod Φφsla polφΦka na ukazatel
  65.  *fin2p;    //ukazatele na ·lo₧iÜt∞ (v po°adφ, v jakΘm se zaplnφ)
  66.  
  67. //hlaviΦka pozice p°i prohledßvßnφ do hloubky
  68. struct Hdr2 {
  69.  Pchar parent;
  70.  int eval;
  71.  PMove lastMove;
  72.  short dist;
  73. };
  74. const int DHDR2= 14;
  75.  
  76. //hlaviΦka pozice p°i prohledßvßnφ do Üφ°ky
  77. struct Hdr3 {
  78.  Pchar parent;
  79.  short mov,pus;
  80.  PMove movesBeg,movesEnd;
  81.  bool dual;
  82. };
  83. const int DHDR3= 17;
  84.  
  85. //hlaviΦka pozice p°i Dijkstrov∞ algoritmu
  86. struct Hdr1 {
  87.  Pchar parent;
  88.  int eval;
  89.  int heapItem;
  90.  PMove lastMove;
  91.  bool dual;
  92. };
  93. const int DHDR1= 17;
  94.  
  95. //hlaviΦka pozice p°i generovßnφ zadßnφ
  96. struct Hdr4 {
  97.  short mov,pus;
  98.  PMove movesBeg,movesEnd;
  99. };
  100. const int DHDR4= 12;
  101.  
  102. typedef Hdr1 *PHdr1;
  103. typedef Hdr2 *PHdr2;
  104. typedef Hdr3 *PHdr3;
  105. typedef Hdr4 *PHdr4;
  106. #define HDR1(p) ((Hdr1*)(p-DHDR1))
  107. #define HDR2(p) ((Hdr2*)(p-DHDR2))
  108. #define HDR3(p) ((Hdr3*)(p-DHDR3))
  109. #define HDR4(p) ((Hdr4*)(p-DHDR4))
  110.  
  111. Pchar backtrack(PMove Umoves, int movpus) ;
  112.  
  113. //-------------------------------------------------------------------
  114. inline void wrXY0(Pchar p, int i)
  115. {
  116.  if(DXY==1) *((BYTE*)p) = (BYTE)i;
  117.  else *((WORD*)p) = (WORD)i;
  118. }
  119.  
  120. inline void wrXY(Pchar &p, int i)
  121. {
  122.  if(DXY==1) *((BYTE*)p) = (BYTE)i, p++;
  123.  else *((WORD*)p) = (WORD)i, p+=2;
  124. }
  125.  
  126. inline int rdXY(void *p)
  127. {
  128.  if(DXY==1) return *((BYTE*)p);
  129.  else return *((WORD*)p);
  130. }
  131.  
  132. void noMem()
  133. {
  134.   msg(lng(768,"Not enough memory"));
  135. }
  136. //-------------------------------------------------------------------
  137. //nalezenφ nejkratÜφ cesty mezi src a dest (bez p°esunu beden)
  138. //do polφ zapφÜe hodnoty dist, distId
  139. void findDist(Psquare src, Psquare dest)
  140. {
  141.  int i,d;
  142.  Psquare *p1,*p2,pn;
  143.  
  144.  distId++;
  145.  src->distId=distId;
  146.  src->dist=0;
  147.  distBuf1[0]=src;
  148.  distBuf1[1]=0;
  149.  for(d=1; ; d++){
  150.    if(d&1) p1=distBuf1,p2=distBuf2;
  151.    else p1=distBuf2,p2=distBuf1;
  152.    if(!*p1) break;
  153.    for( ; *p1; p1++){
  154.      for(i=0; i<4; i++){
  155.        pn= nxtP(*p1,i);
  156.        if(pn->distId!=distId){
  157.          if(pn->obj==BM_GROUND){
  158.            pn->distId=distId;
  159.            pn->dist=d;
  160.            *p2++=pn;
  161.          }else{
  162.            pn->dist=MAXDIST;
  163.          }
  164.        }
  165.      }
  166.      if(*p1==dest) return;
  167.    }
  168.    *p2=0;
  169.  }
  170. }
  171. //-------------------------------------------------------------------
  172. #ifndef NDEBUG
  173. int testPos(Pchar prevPos)
  174. {
  175.  Pchar v;
  176.  int i;           
  177.  Psquare p;
  178.  
  179.  for(v=prevPos+DXY; v<prevPos+posSize1; v+=DXY){
  180.    i=rdXY(v);
  181.    for(p=board; p->i!=i || p->obj!=BM_OBJECT; p++){
  182.      if(p==boardk){
  183.        return 0;
  184.      }
  185.    }
  186.  }
  187.  for(v=prevPos+2*DXY; v<prevPos+posSize1; v+=DXY){
  188.    if(rdXY(v)<=rdXY(v-DXY)) return 0;
  189.  }
  190.  return 1;
  191. }
  192. #endif
  193. //-------------------------------------------------------------------
  194. #define finOrWall(p) ((p)->obj!=BM_WALL && !(p)->store)
  195.  
  196. int testDead(Psquare p)
  197. {
  198.  Psquare pU,pD,pU2,pD2;
  199.  
  200.  pU=nxtP(p,2); pU2=nxtP(pU,2);
  201.  pD=nxtP(p,3); pD2=nxtP(pD,3);
  202.  if((p+1)->obj!=BM_GROUND){
  203.    if(pD->obj!=BM_GROUND){
  204.      if((pD+1)->obj!=BM_GROUND)
  205.        if(!p->store || finOrWall(p+1) || finOrWall(pD) || finOrWall(pD+1)) return 1;
  206.      if((pD+2)->obj!=BM_GROUND && (pD2+1)->obj!=BM_GROUND && (pD2+2)->obj!=BM_GROUND)
  207.        if(!(pD+1)->store && !p->store) return 1;
  208.    }else{
  209.      if((pD2)->obj!=BM_GROUND){
  210.        if((pD-1)->obj!=BM_GROUND &&
  211.           (pD+1)->obj!=BM_GROUND && (pD2-1)->obj!=BM_GROUND
  212.        || (pD2+1)->obj!=BM_GROUND && (pD-1)->obj==BM_WALL &&
  213.           (pD+2)->obj==BM_WALL && !(pD+1)->store)
  214.          if(!(pD)->store && !p->store) return 1;
  215.      }
  216.    }
  217.    if(pU->obj!=BM_GROUND){
  218.      if((pU+1)->obj!=BM_GROUND)
  219.        if(!p->store || finOrWall(p+1) || finOrWall(pU) || finOrWall(pU+1)) return 1;
  220.      if((pU+2)->obj!=BM_GROUND && (pU2+1)->obj!=BM_GROUND && (pU2+2)->obj!=BM_GROUND)
  221.        if(!(pU+1)->store && !p->store) return 1;
  222.    }else{
  223.      if((pU2)->obj!=BM_GROUND){
  224.        if((pU+1)->obj!=BM_GROUND &&
  225.           (pU-1)->obj!=BM_GROUND && (pU2-1)->obj!=BM_GROUND
  226.        || (pU2+1)->obj!=BM_GROUND && (pU-1)->obj==BM_WALL &&
  227.           (pU+2)->obj==BM_WALL && !(pU+1)->store)
  228.          if(!(pU)->store && !p->store) return 1;
  229.      }
  230.    }
  231.  }else{
  232.    if((p+2)->obj!=BM_GROUND){
  233.      if(((pD)->obj!=BM_GROUND && (pD+2)->obj!=BM_GROUND &&
  234.         (pU+1)->obj==BM_WALL && (pD2+1)->obj==BM_WALL && !(pD+1)->store
  235.      || (pU)->obj!=BM_GROUND && (pU+2)->obj!=BM_GROUND &&
  236.         (pD+1)->obj==BM_WALL && (pU2+1)->obj==BM_WALL && !(pU+1)->store)
  237.      || (pU+1)->obj!=BM_GROUND && (pD+1)->obj!=BM_GROUND &&
  238.         ((pU)->obj!=BM_GROUND && (pD+2)->obj!=BM_GROUND ||
  239.          (pD)->obj!=BM_GROUND && (pU+2)->obj!=BM_GROUND))
  240.          if(!(p+1)->store && !p->store) return 1;
  241.    }
  242.  }
  243.  if((p-1)->obj!=BM_GROUND){
  244.    if(pD->obj!=BM_GROUND){
  245.      if((pD-1)->obj!=BM_GROUND)
  246.        if(!p->store || finOrWall(p-1) || finOrWall(pD) || finOrWall(pD-1)) return 1;
  247.      if((pD-2)->obj!=BM_GROUND && (pD2-1)->obj!=BM_GROUND && (pD2-2)->obj!=BM_GROUND)
  248.        if(!(pD-1)->store && !p->store) return 1;
  249.    }else{
  250.      if((pD2)->obj!=BM_GROUND){
  251.        if((pD+1)->obj!=BM_GROUND &&
  252.          (pD-1)->obj!=BM_GROUND && (pD2+1)->obj!=BM_GROUND
  253.        || (pD2-1)->obj!=BM_GROUND && (pD+1)->obj==BM_WALL &&
  254.           (pD-2)->obj==BM_WALL && !(pD-1)->store)
  255.          if(!(pD)->store && !p->store) return 1;
  256.      }
  257.    }
  258.    if(pU->obj!=BM_GROUND){
  259.      if((pU-1)->obj!=BM_GROUND)
  260.        if(!p->store || finOrWall(p-1) || finOrWall(pU) || finOrWall(pU-1)) return 1;
  261.      if((pU-2)->obj!=BM_GROUND && (pU2-1)->obj!=BM_GROUND && (pU2-2)->obj!=BM_GROUND)
  262.        if(!(pU-1)->store && !p->store) return 1;
  263.    }else{
  264.      if((pU2)->obj!=BM_GROUND){
  265.        if((pU+1)->obj!=BM_GROUND &&
  266.          (pU-1)->obj!=BM_GROUND && (pU2+1)->obj!=BM_GROUND
  267.        || (pU2-1)->obj!=BM_GROUND && (pU+1)->obj==BM_WALL &&
  268.           (pU-2)->obj==BM_WALL && !(pU-1)->store)
  269.          if(!(pU)->store && !p->store) return 1;
  270.      }
  271.    }
  272.  }else{
  273.    if((p-2)->obj!=BM_GROUND){
  274.      if(((pD)->obj!=BM_GROUND && (pD-2)->obj!=BM_GROUND &&
  275.         (pU-1)->obj==BM_WALL && (pD2-1)->obj==BM_WALL && !(pD-1)->store
  276.      || (pU)->obj!=BM_GROUND && (pU-2)->obj!=BM_GROUND &&
  277.         (pD-1)->obj==BM_WALL && (pU2-1)->obj==BM_WALL && !(pU-1)->store)
  278.      || (pU-1)->obj!=BM_GROUND && (pD-1)->obj!=BM_GROUND &&
  279.         ((pU)->obj!=BM_GROUND && (pD-2)->obj!=BM_GROUND ||
  280.          (pD)->obj!=BM_GROUND && (pU-2)->obj!=BM_GROUND))
  281.          if(!(p-1)->store && !p->store) return 1;
  282.    }
  283.  }
  284.  return 0;
  285. }
  286. //-------------------------------------------------------------------
  287. //nalezenφ dosa₧iteln²ch objekt∙ a vygenerovßnφ tah∙
  288. PMove findObjects(PMove Umoves)
  289. {
  290.  Psquare pn,pnn,*p1,*p2;
  291.  int i,d;
  292.  
  293.  distId++;
  294.  mover->distId=distId;
  295.  mover->dist=0;
  296.  distBuf1[0]=mover;
  297.  distBuf1[1]=0;
  298.  for(d=1; ; d++){
  299.    if(d&1) p1=distBuf1,p2=distBuf2;
  300.    else p1=distBuf2,p2=distBuf1;
  301.    if(!*p1) break;
  302.    for( ; *p1; p1++){
  303.      for(i=0; i<4; i++){
  304.        pn= nxtP(*p1,i);
  305.        if(pn->distId!=distId && pn->obj==BM_GROUND){
  306.          pn->distId=distId;
  307.          pn->dist=d;
  308.          *p2++=pn;
  309.        }
  310.        else if(pn->obj==BM_OBJECT){
  311.          pnn= nxtP(pn,i);
  312.          if(pnn->obj==BM_GROUND && pnn->finalDist<MAXDIST){
  313.            Umoves->obj=pn;
  314.            Umoves->next=pnn;
  315.            Umoves->dist=(short)d;
  316.            Umoves->direct=(short)i;
  317.            Umoves++;
  318.          }
  319.        }
  320.      }
  321.    }
  322.    *p2=0;
  323.  }
  324.  return Umoves;
  325. }
  326. //-------------------------------------------------------------------
  327. PMove findObjectsR(PMove Umoves)
  328. {
  329.  Psquare pn,pnn,*p1,*p2;
  330.  int i,d;
  331.  
  332.  distId++;
  333.  mover->distId=distId;
  334.  mover->dist=0;
  335.  distBuf1[0]=mover;
  336.  distBuf1[1]=0;
  337.  for(d=1; ; d++){
  338.    if(d&1) p1=distBuf1,p2=distBuf2;
  339.    else p1=distBuf2,p2=distBuf1;
  340.    if(!*p1) break;
  341.    for( ; *p1; p1++){
  342.      for(i=0; i<4; i++){
  343.        pn= nxtP(*p1,i);
  344.        if(pn->distId!=distId && pn->obj==BM_GROUND){
  345.          pn->distId=distId;
  346.          pn->dist=d;
  347.          *p2++=pn;
  348.        }
  349.        else if(pn->obj==BM_OBJECT){
  350.          pnn= prvP(*p1,i);
  351.          if(pnn->obj==BM_GROUND){
  352.            Umoves->obj=pn;
  353.            Umoves->next=*p1;
  354.            Umoves->dist=(short)d;
  355.            Umoves->direct=(short)i;
  356.            Umoves++;
  357.          }
  358.        }
  359.      }
  360.    }
  361.    *p2=0;
  362.  }
  363.  return Umoves;
  364. }
  365. //-------------------------------------------------------------------
  366. PMove findObjectsD(PMove Umoves, Psquare o, int dir)
  367. {
  368.  Psquare pn,pnn,*p1,*p2;
  369.  int i,d;
  370.  bool found;
  371.  
  372.  distId++;
  373.  mover->distId=distId;
  374.  mover->dist=0;
  375.  distBuf1[0]=mover;
  376.  distBuf1[1]=0;
  377.  for(d=1; ; d++){
  378.    if(d&1) p1=distBuf1,p2=distBuf2;
  379.    else p1=distBuf2,p2=distBuf1;
  380.    if(!*p1) break;
  381.    for( ; *p1; p1++){
  382.      found=false;
  383.      for(i=0; i<4; i++){
  384.        pn= nxtP(*p1,i);
  385.        if(pn->distId!=distId && pn->obj==BM_GROUND){
  386.          pn->distId=distId;
  387.          pn->dist=d;
  388.          *p2++=pn;
  389.        }
  390.        else if(pn->obj==BM_OBJECT){
  391.          pnn= prvP(*p1,i);
  392.          if(pnn->obj==BM_GROUND){
  393.            found=true;
  394.          }
  395.        }
  396.      }
  397.      if(found){
  398.        Umoves->next=*p1;
  399.        Umoves->dist=(short)d;
  400.        Umoves->obj=o;
  401.        Umoves->direct=(short)dir;
  402.        Umoves++;
  403.      }
  404.    }
  405.    *p2=0;
  406.  }
  407.  return Umoves;
  408. }
  409. //-------------------------------------------------------------------
  410. void makeMove(Pchar newPos, Pchar prevPos, Move &curMove)
  411. {
  412.  Pchar v,v1;
  413.  
  414.  memcpy(newPos,prevPos,posSize);
  415.  //nalezni posledn∞ p°esunut² objekt
  416.  for(v=newPos+DXY; rdXY(v)!=curMove.obj->i; v+=DXY) ;
  417.  //set°id pozici
  418.  if(curMove.next->i < curMove.obj->i){
  419.    for(v1=v-DXY; rdXY(v1)>curMove.next->i && v1>newPos; v1-=DXY){
  420.      wrXY0(v1+DXY,rdXY(v1));
  421.    }
  422.    wrXY0(v1+DXY,curMove.next->i);
  423.  }
  424.  else{
  425.    for(v1=v+DXY; v1<newPos+posSize1 && rdXY(v1)<curMove.next->i; v1+=DXY){
  426.      wrXY0(v1-DXY,rdXY(v1));
  427.    }
  428.    wrXY0(v1-DXY,curMove.next->i);
  429.  }
  430.  //pozice hrßΦe
  431.  wrXY0(newPos,curMove.obj->i);
  432.  assert(testPos(newPos));
  433. }
  434. //-------------------------------------------------------------------
  435. //v²poΦet hashovacφ funkce
  436. Pchar *hash(Pchar pos)
  437. {
  438.  DWORD h;
  439.  Pchar posEnd;
  440.  
  441.  h=0;
  442.  posEnd= pos+posSize1;
  443.  for( ; pos<posEnd; pos++){
  444.    h= (h + (DWORD)*(Puchar)pos)*1234567;
  445. //   h= h = (h << 5) + h + *(Puchar)pos;
  446.  }
  447.  return &hashTable[h%DhashTable];
  448. }
  449. //-------------------------------------------------------------------
  450. //p°ed touto funkcφ musφ b²t zavolßno findObjects
  451. int testBlocked(Pchar prevPos, PMove lastMove, PMove Umoves)
  452. {
  453.  Psquare p,p0,pn,*p1,*p2;
  454.  Pchar curPos,v1,v2,found,w;
  455.  int i,d,posSize0,result,finalDone0;
  456.  
  457.  if(!lastMove) return 0;
  458.  //podφvej se okolo poslednφho tahu
  459.  p0=lastMove->next;
  460.  p1=distBuf1;
  461.  for(i=0; i<8; i++){
  462.    p=nxtP(p0,i);
  463.    if(p->obj==BM_GROUND && p->distId!=distId){
  464.      *p1++=p;
  465.      p->distId=distId+1;
  466.    }
  467.  }
  468.  if(p1-distBuf1==0) return 0;
  469.  if(UposTable==posTablek) return 0;
  470.  *p1=0;
  471.  //najdi objekty sousedφcφ s nedosa₧itelnou oblastφ
  472.  distId++;
  473.  for(d=1; ; d++){
  474.    if(d&1) p1=distBuf1,p2=distBuf2;
  475.    else p1=distBuf2,p2=distBuf1;
  476.    if(!*p1) break;
  477.    for( ; *p1; p1++){
  478.      for(i=0; i<8; i++){
  479.        pn= nxtP(*p1,i);
  480.        if(pn->distId!=distId){
  481.          if(pn->obj==BM_OBJECT){
  482.            pn->distId=distId;
  483.          }
  484.          else if(pn->obj==BM_GROUND && i<4){
  485.            pn->distId=distId;
  486.            *p2++=pn;
  487.          }
  488.        }
  489.      }
  490.    }
  491.    *p2=0;
  492.  }
  493.  //testovacφ pozice zapisuj od konce alokovanΘ pam∞ti
  494.  if(!testing){
  495.    w=posTablek;
  496.    posTablek=UposTable-posSize2;
  497.    UposTable= w-posSize2;
  498.    posSize2= -posSize2;
  499.  }
  500.  //vytvo° novou pozici, kterß mß mΘn∞ objekt∙
  501.  curPos= UposTable;
  502.  v2=curPos+DXY;
  503.  for(v1=prevPos+DXY; v1<prevPos+posSize1; v1+=DXY){
  504.    p=i2p[rdXY(v1)];
  505.    if(p->distId==distId){
  506.      wrXY(v2,p->i);
  507.    }else{
  508.      p->obj=BM_GROUND;
  509.      #ifdef DEBUG
  510.        paintSquare(p);
  511.      #endif
  512.    }
  513.  }
  514.  //sni₧ posSize1
  515.  posSize0=posSize1;
  516.  posSize1=(int)(v2-curPos);
  517.  result=0;
  518.  if(posSize1<posSize0){
  519.    if(posSize1>2*DXY){
  520.      while(v2!=curPos+posSize){
  521.        wrXY(v2,-1);
  522.      }
  523.      //spus¥ backtracking
  524.      HDR2(curPos)->parent=0;
  525.      HDR2(curPos)->eval=0;
  526.      HDR2(curPos)->lastMove=0;
  527.      finalDone0=finalDone;
  528.      testing++;
  529.      #ifdef DEBUG
  530.        repaint();
  531.        Sleep(10);
  532.      #endif
  533.      found= backtrack(Umoves,0);
  534.      if(found){
  535.        HDR2(found)->parent=curPos;
  536.      }else{
  537.        //pozice je ne°eÜitelnß nebo moc slo₧itß
  538.        result=1;
  539.      }
  540.      testing--;
  541.      finalDone=finalDone0;
  542.    }
  543.    //vra¥ zpßtky vÜechny objekty
  544.    posSize1=posSize0;
  545.    for(v1=prevPos+DXY; v1<prevPos+posSize1; v1+=DXY){
  546.      assert(rdXY(v1)>=0 && rdXY(v1)<width*height);
  547.      i2p[rdXY(v1)]->obj=BM_OBJECT;
  548.      #ifdef DEBUG
  549.        paintSquare(i2p[rdXY(v1)]);
  550.      #endif
  551.    }
  552.  }
  553.  if(!testing){
  554.    posSize2= -posSize2;
  555.    w=posTablek;
  556.    posTablek=UposTable+posSize2;
  557.    UposTable= w+posSize2;
  558.  }
  559.  return result;
  560. }
  561. //-------------------------------------------------------------------
  562. /*
  563.  
  564. p°φklad cont pro direct==1
  565.  
  566.  . X X X X X X X X
  567. -1 0 1 1 2 0 1 1 X
  568.  . X X X . X X X X
  569.  
  570. */
  571.  
  572. //protlaΦenφ objektu zkrz celou chodbu
  573. PMove testLastMove(PMove lastMove, PMove Umoves)
  574. {
  575.  if(lastMove && lastMove->next->cont[lastMove->direct]>0){
  576.    Psquare p=nxtP(lastMove->next, lastMove->direct);
  577.    if(p->obj==BM_GROUND && p->finalDist<MAXDIST){
  578.      //tlaΦenφ objektu ve stejnΘm sm∞ru jako p°edchozφ tah
  579.      Umoves->obj= lastMove->next;
  580.      Umoves->next= p;
  581.      Umoves->dist=1;
  582.      Umoves->direct= lastMove->direct;
  583.      Umoves++;
  584.    }
  585.    return Umoves;
  586.  }
  587.  return 0;
  588. }
  589.  
  590. PMove testLastMoveR(PMove lastMove, PMove Umoves)
  591. {
  592.  if(lastMove && lastMove->next->cont[lastMove->direct^1]==1){
  593.    Psquare p=prvP(lastMove->next, lastMove->direct);
  594.    Psquare pn=prvP(p,lastMove->direct);
  595.    assert(p->obj==BM_GROUND);
  596.    assert(lastMove->obj->obj==BM_GROUND);
  597.    assert(lastMove->next->obj==BM_OBJECT);
  598.    if(pn->obj==BM_GROUND){
  599.      //ta₧enφ objektu ve stejnΘm sm∞ru jako p°edchozφ tah
  600.      Umoves->obj= lastMove->next;
  601.      Umoves->next= p;
  602.      Umoves->dist=1;
  603.      Umoves->direct= lastMove->direct;
  604.      Umoves++;
  605.    }
  606.    return Umoves;
  607.  }
  608.  return 0;
  609. }
  610.  
  611. void testLastMoveD(PMove lastMove, PMove Umoves, PMove UmovesEnd)
  612. {
  613.  if(!lastMove) return;
  614.  Psquare pm= prvP(lastMove->obj,lastMove->direct); 
  615.  if(pm->cont[lastMove->direct^1]==1){
  616.    Psquare p=prvP(pm, lastMove->direct);
  617.    assert(p->obj==BM_GROUND);
  618.    assert(lastMove->obj->obj==BM_GROUND);
  619.    assert(pm->obj==BM_OBJECT);
  620.    for(PMove m=Umoves; m<UmovesEnd; m++){
  621.      if(m->obj!=pm || m->direct!=lastMove->direct) m->direct=-1;
  622.    }
  623.  }
  624. }
  625. //-------------------------------------------------------------------
  626. Pchar backtrack(PMove Umoves, int movpus)
  627. {
  628.  Pchar *u,v,newPos,prevPos,found,result=0;
  629.  int m,o,i,f1,f2,movpus1,finalDone0,direct0;
  630.  PMove UmovesEnd,um,bm;
  631.  Psquare mover0,*newMover,p,pn;
  632.  Move curMove;
  633.  
  634.  prevPos=UposTable;
  635.  mover0=mover;
  636.  finalDone0=finalDone;
  637.  //najdi dosa₧itelnΘ objekty
  638.  UmovesEnd= findObjects(Umoves);
  639.  //hrßΦe umφsti do levΘho hornφho rohu
  640.  for(newMover=i2p; (*newMover)->distId!=distId; newMover++) ;
  641.  //do pozice zapiÜ polohu hrßΦe
  642.  wrXY0(prevPos,(*newMover)->i);
  643.  //ukonΦi testBlocked jakmile se lze dostat k objekt∙m ze vÜech stran
  644.  if(testing){
  645.    for(v=prevPos+posSize1-DXY; v>prevPos; v-=DXY){
  646.      p=i2p[rdXY(v)];
  647.      if(!p->store){
  648.        for(i=0; i<4; i++){
  649.          pn=nxtP(p,i);
  650.          if(pn->obj==BM_GROUND && pn->distId!=distId) goto l1;
  651.        }
  652.      }
  653.    }
  654.    return prevPos;
  655.  }
  656.  l1:
  657.  //vypoΦti hashovacφ funkci
  658.  u= hash(prevPos);
  659.  //p°idej novou pozici do tabulky
  660.  for( ;*u; ){
  661.    if(!memcmp(*u,prevPos,posSize)){
  662.      if(testing && HDR2(*u)->parent){
  663.        //pozice je °eÜitelnß
  664.        return *u;
  665.      }
  666.      //neprohledßvej stejnou pozici vφcekrßt
  667.      return 0;
  668.    }
  669.    u++;
  670.    if(u==hashTablek) u=hashTable;
  671.  }
  672.  *u=prevPos;
  673.  UposTable+=posSize2;
  674.  //protlaΦ objekt celou chodbou
  675.  um=testLastMove(HDR2(prevPos)->lastMove, Umoves);
  676.  if(um) UmovesEnd=um;
  677.  //zjisti, jestli poslednφ tah n∞co nezablokoval
  678.  if(testBlocked(prevPos, HDR2(prevPos)->lastMove, UmovesEnd)) return 0;
  679.  //vyzkouÜej postupn∞ vÜechny mo₧nΘ p°esuny
  680.  for( ; Umoves<UmovesEnd; Umoves++){
  681.    newPos=UposTable;
  682.    if(newPos==posTablek) break; //pam∞¥ u₧ je plnß
  683.    bm=Umoves;
  684.    if(0+testing){
  685.      //zvol p°esun sm∞rem do zablokovanΘho prostoru
  686.      m=-1;
  687.      for(um=Umoves; um<UmovesEnd; um++){
  688.        for(i=0; i<4; i++){
  689.          p=nxtP(um->obj,i);
  690.          if(p->obj==BM_GROUND && distId - p->distId > m){
  691.            m = distId - p->distId;
  692.            bm=um;
  693.          }
  694.        }
  695.      }
  696.    }else{
  697.      //vyber objekt, kter² je nejblφ₧e ·lo₧iÜti
  698.      m=0x7fffffff;
  699.      for(um=Umoves; um<UmovesEnd; um++){
  700.        f1= um->obj->finalDists[finalDone];
  701.        f2= um->next->finalDists[finalDone];
  702.        o= (f2<<2) + ((f2-f1)<<5) + um->dist;
  703.        if(um->obj->direct == (um->direct^1)) o+=600; 
  704.        if(o<m){
  705.          m=o;
  706.          bm=um;
  707.        }
  708.      }
  709.    }
  710.    curMove=*bm;
  711.    *bm=*Umoves;
  712.    movpus1= movpus+curMove.dist+1;
  713.    //prove∩ jeden p°esun
  714.    curMove.next->obj= BM_OBJECT;
  715.    curMove.obj->obj= BM_GROUND;
  716.    if(testDead(curMove.next)){
  717.      curMove.next->obj= BM_GROUND;
  718.      curMove.obj->obj= BM_OBJECT;
  719.    }else{
  720.      #ifdef DEBUG
  721.        mover=0;
  722.        paintSquare(curMove.next);
  723.        paintSquare(curMove.obj);
  724.        Sleep(20);
  725.      #endif
  726.      mover=curMove.obj;
  727.      direct0= curMove.next->direct;
  728.      curMove.next->direct= curMove.direct;
  729.      //vytvo° novou pozici
  730.      HDR2(newPos)->parent=0;
  731.      HDR2(newPos)->eval= movpus1;
  732.      HDR2(newPos)->lastMove= &curMove;
  733.      makeMove(newPos,prevPos,curMove);
  734.      //porovnej novou pozici s koncovou pozicφ
  735.      amax(finalDone, curMove.obj->finalDist);
  736.      if(curMove.next->finalDist==finalDone){
  737.        do{
  738.          finalDone++;
  739.        }while(fin2p[finalDone]->obj==BM_OBJECT);
  740.      }
  741.      if(!testing && finalDone==Nstore){
  742.        UfoundPos= newPos;
  743.        HDR2(newPos)->eval=movpus1;
  744.        HDR2(newPos)->parent=prevPos;
  745.        UposTable+=posSize2;
  746.        result=prevPos;
  747.      }else{
  748.        //backtracking
  749.        found=backtrack(UmovesEnd, movpus1);
  750.        if(found){
  751.          HDR2(found)->parent= prevPos;
  752.          assert(testing || HDR2(found)->eval==movpus1);
  753.          HDR2(found)->dist= (short) (curMove.dist+1);
  754.          result=prevPos;
  755.        }
  756.      }
  757.      //vra¥ zp∞t vÜechny zm∞ny
  758.      curMove.next->obj= BM_GROUND;
  759.      curMove.obj->obj= BM_OBJECT;
  760.      #ifdef DEBUG
  761.        mover=0;
  762.        paintSquare(curMove.next);
  763.        paintSquare(curMove.obj);
  764.      #endif
  765.      curMove.next->direct= direct0;
  766.      mover=mover0;
  767.      finalDone=finalDone0;
  768.      if(result) break;
  769.    }
  770.  }
  771.  return result;
  772. }
  773. //-------------------------------------------------------------------
  774. void depthSearch()
  775. {
  776.  int m=mover->i;
  777.  //p°iprav poΦßteΦnφ pozici
  778.  PHdr2 hdr= HDR2(UposTable);
  779.  hdr->parent=0;
  780.  hdr->eval=0;
  781.  hdr->lastMove=0;
  782.  while(fin2p[finalDone]->obj==BM_OBJECT)  finalDone++;
  783.  //spus¥ backtracking
  784.  backtrack(movedObj,0);
  785.  //obnov poΦßteΦnφ pozici hrßΦe
  786.  wrXY0(posTable+DHDR2, m);
  787. }
  788. //-------------------------------------------------------------------
  789. void breadthSearch()
  790. {
  791.  Pchar *u,v,curPos,newPos;
  792.  char *movedObjBeg,*m;
  793.  PHdr3 curPosHdr,newPosHdr,found;
  794.  PMove Umoves,Umoves1,um;
  795.  Psquare p,pn,*pp;
  796.  int i,j;
  797.  bool isDual;
  798.  
  799.  //poΦßteΦnφ pozice
  800.  curPos=UposTable;
  801.  curPosHdr=HDR3(curPos);
  802.  curPosHdr->parent=0;
  803.  curPosHdr->mov=curPosHdr->pus=0;
  804.  curPosHdr->movesBeg= movedObj;
  805.  curPosHdr->movesEnd= Umoves= findObjects(movedObj);
  806.  curPosHdr->dual= false;
  807.  UposTable+=posSize2;
  808.  
  809.  
  810.  ///
  811.  /*
  812.  memcpy(posTable+posSize2,posTable,posSize2);
  813.  findDist(i2p[rdXY(posTable+DHDR)],0);
  814.  for(pp=i2p; (*pp)->distId!=distId; pp++) ;
  815.  wrXY0(UposTable,(*pp)->i);
  816.  newPosHdr=HDR3(UposTable);
  817.  newPosHdr->mov=(short)(*pp)->dist;
  818.  u=hash(UposTable);
  819.  assert(!*u);
  820.  *u=UposTable;
  821.  UposTable+=posSize2;
  822.  */
  823.  
  824.  
  825.  //sma₧ vÜechny objekty
  826.  for(v=curPos+DXY; v<curPos+posSize1; v+=DXY){
  827.    assert(i2p[rdXY(v)]->obj==BM_OBJECT);
  828.    i2p[rdXY(v)]->obj=BM_GROUND;
  829.  }
  830.  //koncovß pozice
  831.  for(i=0; i<Nstore; i++){
  832.    assert(fin2p[i]->obj==BM_GROUND);
  833.    fin2p[i]->obj=BM_OBJECT;
  834.  }
  835.  
  836.  ///curPos=UposTable;
  837.  
  838.  
  839.  //vφce koncov²ch pozic podle umφst∞nφ hrßΦe
  840.  for(p=board; p<boardk; p++){
  841.    p->distId=0;
  842.  }
  843.  for(j=0; j<Nstore; j++){
  844.    p=fin2p[j];
  845.    for(i=0; i<4; i++){
  846.      pn=nxtP(p,i);
  847.      if(!pn->distId && pn->obj==BM_GROUND){
  848.        findDist(pn,0);
  849.        for(pp=i2p; (*pp)->distId!=distId; pp++) ;
  850.        memcpy(UposTable+DXY,finalPos,posSize1-DXY);
  851.        wrXY0(UposTable,(*pp)->i);
  852.        UposTable+=posSize2;
  853.      }
  854.    }
  855.  }
  856.  for(v=curPos+posSize2; v<UposTable; v+=posSize2){
  857.    newPosHdr=HDR3(v);
  858.    newPosHdr->parent=0;
  859.    newPosHdr->mov=curPosHdr->pus=0;
  860.    newPosHdr->dual= true;
  861.    newPosHdr->movesBeg= Umoves;
  862.    mover=i2p[rdXY(v)];
  863.    newPosHdr->movesEnd= findObjectsR(Umoves);
  864.    ///
  865.    for(um=Umoves; um<newPosHdr->movesEnd; um++)  um->dist=1;
  866.  
  867.    Umoves= newPosHdr->movesEnd;
  868.  }
  869.  //sma₧ vÜechny objekty
  870.  for(i=0; i<Nstore; i++){
  871.    assert(fin2p[i]->obj==BM_OBJECT);
  872.    fin2p[i]->obj=BM_GROUND;
  873.  }
  874.  movedObjBeg=(char*)movedObj+65536;
  875.  //cyklus p°es vÜechny nalezenΘ pozice
  876.  for( ;curPos<UposTable; curPos+=posSize2){
  877.    curPosHdr= HDR3(curPos);
  878.    isDual= curPosHdr->dual;
  879.    //vytvo° aktußlnφ pozici
  880.    for(v=curPos+DXY; v<curPos+posSize1; v+=DXY){
  881.      assert(i2p[rdXY(v)]->obj==BM_GROUND);
  882.      i2p[rdXY(v)]->obj=BM_OBJECT;
  883.    }
  884.    //uvolni tahy, kterΘ u₧ byly zpracovßny
  885.    m= (char*)( (int)curPosHdr->movesBeg & -65536 );
  886.    i= m-movedObjBeg;
  887.    if(i>5000000){
  888.      VirtualFree(movedObjBeg,i,MEM_DECOMMIT);
  889.      movedObjBeg=m;
  890.    }
  891.    //vyzkouÜej vÜechny mo₧nΘ p°esuny
  892.    for(Umoves1=curPosHdr->movesBeg; Umoves1<curPosHdr->movesEnd && Umoves1->direct>=0; Umoves1++){
  893.      Move &curMove= *Umoves1;
  894.      newPos=UposTable;
  895.      if(newPos==posTablek) break;
  896.      newPosHdr=HDR3(newPos);
  897.      //prove∩ tah
  898.      assert(testPos(curPos));
  899.      assert(curMove.next->obj==BM_GROUND);
  900.      assert(curMove.obj->obj==BM_OBJECT);
  901.      curMove.next->obj= BM_OBJECT;
  902.      curMove.obj->obj= BM_GROUND;
  903.      if(isDual || !testDead(curMove.next)){
  904.        //vytvo° novou pozici                 
  905.        mover= isDual ? prvP(curMove.next,curMove.direct) : curMove.obj;
  906.        makeMove(newPos,curPos,curMove);
  907.        newPosHdr->mov= (short)(curPosHdr->mov + curMove.dist);
  908.        newPosHdr->pus= (short)(curPosHdr->pus + 1);
  909.        newPosHdr->dual= isDual;
  910.        //najdi vÜechny mo₧nΘ p°esuny v novΘ pozici
  911.        newPosHdr->movesEnd= isDual ? findObjectsR(Umoves) : findObjects(Umoves);
  912.        //hrßΦe dej do levΘho hornφho rohu
  913.        for(pp=i2p; (*pp)->distId!=distId; pp++) ;
  914.        wrXY0(newPos,(*pp)->i);
  915.        //vypoΦti hashovacφ funkci
  916.        u=hash(newPos);
  917.        for(;;){
  918.          if(!*u){
  919.            //p°idej novou pozici do tabulky
  920.            *u=newPos;
  921.            UposTable+=posSize2;
  922.            newPosHdr->parent= curPos;
  923.            newPosHdr->movesBeg= Umoves;
  924.            if(1 || !isDual){ ///
  925.              um= (isDual ? testLastMoveR:testLastMove)(&curMove, Umoves);
  926.              if(um) um->direct=-1;
  927.            }
  928.            if(!isDual && testBlocked(newPos, &curMove, newPosHdr->movesEnd)){///
  929.              //pozice nebude mφt ₧ßdnΘ tahy
  930.              newPosHdr->movesEnd= Umoves;
  931.            }else{
  932.              Umoves= newPosHdr->movesEnd;
  933.            }
  934.            #ifdef DEBUG
  935.              repaint();
  936.              Sleep(1);
  937.            #endif
  938.            break;
  939.          }
  940.          if(!memcmp(*u,newPos,posSize)){
  941.            //pozice byla v tabulce nalezena
  942.            found=HDR3(*u);
  943.            if(found->dual!=isDual){
  944.              newPosHdr->parent= curPos;
  945.              if(isDual){
  946.                UfoundPos=*u;
  947.                UfoundPosD=newPos;
  948.              }else{
  949.                UfoundPosD=*u;
  950.                UfoundPos=newPos;
  951.              }
  952.              return;
  953.            }
  954.            if(found->pus == newPosHdr->pus &&
  955.               found->mov > newPosHdr->mov){
  956.              //nalezeno lepÜφ °eÜenφ
  957.              found->mov= newPosHdr->mov;
  958.              found->parent= curPos;
  959.              if(found->movesEnd > found->movesBeg){
  960.                assert(newPosHdr->movesEnd-Umoves==found->movesEnd-found->movesBeg);
  961.                memcpy(found->movesBeg,Umoves,(char*)newPosHdr->movesEnd-(char*)Umoves);
  962.              }
  963.            }
  964.            break;
  965.          }
  966.          u++;
  967.          if(u==hashTablek) u=hashTable;
  968.        }
  969.      }
  970.      //vra¥ tah zp∞t
  971.      curMove.next->obj= BM_GROUND;
  972.      curMove.obj->obj= BM_OBJECT;
  973.    }
  974.    //sma₧ vÜechny objekty
  975.    for(v=curPos+DXY; v<curPos+posSize1; v+=DXY){
  976.      assert(i2p[rdXY(v)]->obj==BM_OBJECT);
  977.      i2p[rdXY(v)]->obj=BM_GROUND;
  978.    }
  979.    if(UposTable==posTablek) break; //pam∞¥ u₧ je plnß
  980.  }
  981. }
  982. //-------------------------------------------------------------------
  983. void addToHash(Pchar pos)
  984. {
  985.  Pchar *u;
  986.  
  987.  u=hash(pos);
  988.  while(*u){
  989.    u++;
  990.    if(u==hashTablek) u=hashTable;
  991.  }
  992.  *u=pos;
  993. }
  994. //-------------------------------------------------------------------
  995. void dijkstra()
  996. {
  997.  int i,j,heapSize,foundEval,movpus1,x;
  998.  Pchar *u,v,curPos,newPos;
  999.  PHdr1 curPosHdr,newPosHdr,*heap,h;
  1000.  PMove Umoves,UmovesEnd,um;
  1001.  Psquare p,pn,pr,pnn;
  1002.  bool isDual;
  1003.  
  1004.  foundEval=0x7fffffff;
  1005.  //halda obsahuje ukazatele na pozice
  1006.  heap= new PHdr1[maxPos];
  1007.  //poΦßteΦnφ pozice
  1008.  curPos=UposTable;
  1009.  heap[curPosHdr->heapItem=heapSize=1]= curPosHdr= HDR1(curPos);
  1010.  curPosHdr->parent=0;
  1011.  curPosHdr->eval=0;
  1012.  curPosHdr->lastMove=0;
  1013.  curPosHdr->dual=false;
  1014.  addToHash(UposTable);
  1015.  UposTable+=posSize2;
  1016.  //sma₧ vÜechny objekty
  1017.  for(v=curPos+DXY; v<curPos+posSize1; v+=DXY){
  1018.    assert(i2p[rdXY(v)]->obj==BM_OBJECT);
  1019.    i2p[rdXY(v)]->obj=BM_GROUND;
  1020.  }
  1021.  //vφce koncov²ch pozic - vedle ka₧dΘho objektu
  1022.  for(j=0; j<Nstore; j++){
  1023.    p=fin2p[j];
  1024.    for(i=0; i<4; i++){
  1025.      pn=nxtP(p,i);
  1026.      if(pn->obj==BM_GROUND && !pn->store){
  1027.        pnn=nxtP(pn,i);
  1028.        if(pnn->obj==BM_GROUND && !pnn->store){
  1029.          memcpy(UposTable+DXY,finalPos,posSize1-DXY);
  1030.          wrXY0(UposTable,pn->i);
  1031.          h= HDR1(UposTable);
  1032.          heap[h->heapItem=++heapSize]=h;
  1033.          h->parent=0;
  1034.          h->eval=0;
  1035.          h->lastMove=0;
  1036.          h->dual=true;
  1037.          addToHash(UposTable);
  1038.          UposTable+=posSize2;
  1039.        }
  1040.      }
  1041.    }
  1042.  }
  1043.  Umoves=movedObj;
  1044.  //cyklus p°es vÜechny nalezenΘ pozice
  1045.  for( ;heapSize; ){
  1046.    //vezmi vrchol heapu - pozice s nejmenÜφm moves+pushes
  1047.    curPosHdr= heap[1];
  1048.    curPosHdr->heapItem=0;
  1049.    curPos= ((Pchar)curPosHdr)+DHDR1;
  1050.    isDual= curPosHdr->dual;
  1051.    //odstra≥ vrchol heapu
  1052.    x=heap[heapSize]->eval;
  1053.    j=1;
  1054.    i=2;
  1055.    while(i<heapSize){
  1056.      if(i+1 < heapSize && heap[i]->eval > heap[i+1]->eval) i++;
  1057.      if(x <= heap[i]->eval) break;
  1058.      heap[j]=heap[i];
  1059.      heap[j]->heapItem=j;
  1060.      j=i;
  1061.      i*=2;
  1062.    }
  1063.    heap[j]=heap[heapSize];
  1064.    heap[j]->heapItem=j;
  1065.    heapSize--;
  1066.    //vytvo° aktußlnφ pozici
  1067.    mover= i2p[rdXY(curPos)];
  1068.    for(v=curPos+DXY; v<curPos+posSize1; v+=DXY){
  1069.      assert(i2p[rdXY(v)]->obj==BM_GROUND);
  1070.      i2p[rdXY(v)]->obj=BM_OBJECT;
  1071.    }
  1072.    if(curPos==UfoundPos || curPos==UfoundPosD) goto end;
  1073.    //najdi vÜechny mo₧nΘ p°esuny v aktußlnφ pozici
  1074.    if(!isDual){
  1075.      UmovesEnd=findObjects(Umoves);
  1076.    }else{
  1077.      UmovesEnd=Umoves;
  1078.      p=mover;
  1079.      for(i=0; i<4; i++){
  1080.        pn=nxtP(p,i);
  1081.        if(pn->obj==BM_OBJECT){
  1082.          pr=prvP(p,i);
  1083.          if(pr->obj==BM_GROUND){
  1084.            mover=pr;
  1085.            p->obj=BM_OBJECT;
  1086.            pn->obj=BM_GROUND;
  1087.            UmovesEnd=findObjectsD(UmovesEnd,pn,i);
  1088.            pn->obj=BM_OBJECT;
  1089.            p->obj=BM_GROUND;
  1090.          }
  1091.        }
  1092.      }
  1093.      mover=p;
  1094.    }
  1095.    if(!isDual){
  1096.      um= testLastMove(curPosHdr->lastMove, Umoves);
  1097.      if(um) UmovesEnd=um;
  1098.    }else{
  1099.      testLastMoveD(curPosHdr->lastMove,Umoves,UmovesEnd);
  1100.    }
  1101.    if(1 || !testBlocked(curPos, curPosHdr->lastMove, UmovesEnd)){
  1102.      for(; Umoves<UmovesEnd; Umoves++){
  1103.        newPos=UposTable;
  1104.        if(newPos==posTablek) break;
  1105.        newPosHdr=HDR1(newPos);
  1106.        assert(testPos(curPos));
  1107.        //prove∩ tah
  1108.        Move &curMove= *Umoves;
  1109.        if(curMove.direct<0) continue;
  1110.        assert(curMove.obj->obj==BM_OBJECT);
  1111.        curMove.obj->obj= BM_GROUND;
  1112.        mover= curMove.obj;
  1113.        if(isDual){
  1114.          mover= curMove.next;
  1115.          curMove.next= prvP(curMove.obj,curMove.direct);
  1116.        }
  1117.        assert(curMove.next->obj==BM_GROUND);
  1118.        curMove.next->obj= BM_OBJECT;
  1119.        if(isDual || !testDead(curMove.next)){
  1120.          //vytvo° novou pozici
  1121.          makeMove(newPos,curPos,curMove);
  1122.          wrXY0(newPos,mover->i);
  1123.          movpus1= curPosHdr->eval + curMove.dist + 1;
  1124.          //vypoΦti hashovacφ funkci
  1125.          u=hash(newPos);
  1126.          for(;;){
  1127.            if(!*u){
  1128.              //p°idej novou pozici do tabulky
  1129.              *u=newPos;
  1130.              newPosHdr->dual=isDual;
  1131.              UposTable+=posSize2;
  1132.              //zv∞tÜi velikost heapu
  1133.              newPosHdr->heapItem= ++heapSize;
  1134.              #ifdef DEBUG
  1135.                repaint();
  1136.                Sleep(1);
  1137.              #endif
  1138.              break;
  1139.            }
  1140.            if(rdXY(*u)==rdXY(newPos) && !memcmp(*u,newPos,posSize)){
  1141.              //pozice byla v tabulce nalezena
  1142.              h=HDR1(*u);
  1143.              //test setkßnφ dop°ednΘho a dußlnφho °eÜenφ
  1144.              if(h->dual!=isDual){
  1145.                if(!h->heapItem && movpus1+h->eval < foundEval){///
  1146.                  foundEval= movpus1+h->eval;
  1147.                  if(isDual){
  1148.                    UfoundPos=*u;
  1149.                    UfoundPosD=curPos;
  1150.                  }else{
  1151.                    UfoundPosD=*u;
  1152.                    UfoundPos=curPos;
  1153.                  }
  1154.                }
  1155.                goto nxt;
  1156.              }
  1157.              newPos=*u;
  1158.              newPosHdr= HDR1(newPos);
  1159.              assert(!newPosHdr->parent || newPosHdr->parent>=posTable && newPosHdr->parent<posTablek);
  1160.              if(newPosHdr->eval <= movpus1) goto nxt;
  1161.              //nalezeno lepÜφ °eÜenφ
  1162.              break;
  1163.            }
  1164.            u++;
  1165.            if(u==hashTablek) u=hashTable;
  1166.          }
  1167.          //oprav set°φd∞nφ heapu
  1168.          newPosHdr->parent= curPos;
  1169.          newPosHdr->eval= movpus1;
  1170.          newPosHdr->lastMove= &curMove;
  1171.          j= newPosHdr->heapItem;
  1172.          i=j/2;
  1173.          while(i>0 && heap[i]->eval > movpus1){
  1174.            heap[j]=heap[i];
  1175.            heap[j]->heapItem=j;
  1176.            j=i;
  1177.            i/=2;
  1178.          }
  1179.          heap[j]= newPosHdr;
  1180.          newPosHdr->heapItem=j;
  1181.        }
  1182.        nxt:
  1183.        //vra¥ tah zp∞t
  1184.        curMove.next->obj= BM_GROUND;
  1185.        curMove.obj->obj= BM_OBJECT;
  1186.      }
  1187.    }
  1188.    //sma₧ vÜechny objekty
  1189.    for(v=curPos+DXY; v<curPos+posSize1; v+=DXY){
  1190.      assert(i2p[rdXY(v)]->obj==BM_OBJECT);
  1191.      i2p[rdXY(v)]->obj=BM_GROUND;
  1192.    }
  1193.    if(UposTable==posTablek) break;
  1194.  }
  1195.  end:
  1196.  delete[] heap;
  1197.  if(UfoundPos){
  1198.  
  1199.  }
  1200. }
  1201. //-------------------------------------------------------------------
  1202. void delBlind()
  1203. {
  1204.  Psquare p,pn,pn1;
  1205.  int i,j,i1;
  1206.  
  1207.  //sma₧ slepΘ uliΦky
  1208.  UfirstMove= firstMove= new char[width*height/2];
  1209.  for(p=board; p<boardk; p++){
  1210.    if(p->obj==BM_GROUND && !p->store){
  1211.      j=0;
  1212.      for(i=0; i<4; i++){
  1213.        pn=nxtP(p,i);
  1214.        if(pn->obj!=BM_WALL){
  1215.           j++;
  1216.           pn1=pn;
  1217.           i1=i;
  1218.        }
  1219.      }
  1220.      if(j==1){
  1221.        if(p==mover){
  1222.          if(pn1->obj==BM_OBJECT){
  1223.            if(nxtP(pn1,i1)->obj!=BM_GROUND || pn1->store){
  1224.              continue;
  1225.            }
  1226.            pn1->obj=BM_GROUND;
  1227.            nxtP(pn1,i1)->obj=BM_OBJECT;
  1228.            *UfirstMove++ = char('4'+i1);
  1229.          }else{
  1230.            *UfirstMove++ = char('0'+i1);
  1231.          }
  1232.          mover=pn1;
  1233.        }
  1234.        p->obj=BM_WALL;
  1235.        p=board;
  1236.      }
  1237.    }
  1238.  }
  1239. }
  1240. //-------------------------------------------------------------------
  1241. int thinkInit()
  1242. {
  1243.  Psquare p,pn,pnn,*p1,*p2,*pf,*ps,po[4];
  1244.  int i,j,jm,m,d,k,w,*UfinA,*finRadius;
  1245.  Pchar UfinalPos,UstartPos;
  1246.  
  1247.  Nobj=Nstore=i=0;
  1248.  for(p=board; p<boardk; p++){
  1249.    if(p->obj==BM_GROUND || p->obj==BM_OBJECT){
  1250.      p->i=i++;
  1251.      for(j=0; j<4; j++){
  1252.        po[j]=nxtP(p,j);
  1253.        p->cont[j]=-1;
  1254.      }
  1255.      if(po[0]->obj!=BM_WALL && po[1]->obj!=BM_WALL &&
  1256.         po[2]->obj==BM_WALL && po[3]->obj==BM_WALL){
  1257.        p->cont[0]=p->cont[1]=1;
  1258.      }
  1259.      else if(po[0]->obj==BM_WALL && po[1]->obj==BM_WALL &&
  1260.         po[2]->obj!=BM_WALL && po[3]->obj!=BM_WALL){
  1261.        p->cont[2]=p->cont[3]=1;
  1262.      }
  1263.    }else{
  1264.      p->i=-1;
  1265.    }
  1266.    if(p->obj==BM_OBJECT) Nobj++;
  1267.    if(p->store) Nstore++;
  1268.    p->distId=0;
  1269.  }
  1270.  Nground=i;
  1271.  UfinA= finalDistA= new int[i*Nstore];
  1272.  i2p= new Psquare[i];
  1273.  fin2p= new Psquare[Nstore+1];
  1274.  DXY=1;
  1275.  if(i>255) DXY=sizeof(WORD);
  1276.  if(Nobj) maxPos= maxMem*1000000/4/sizeof(Move)/Nstore;
  1277.  aminmax(maxPos,100,maxPos0);
  1278.  const int D[]={DHDR2,DHDR3,DHDR1,DHDR4};
  1279.  DHDR= D[algorithm];
  1280.  distId=0;
  1281.  posSize1= posSize= (Nobj+1)*DXY;
  1282.  posSize2= posSize1+DHDR;
  1283.  DhashTable= maxPos*2+17;
  1284.  hashTable= new char*[DhashTable];
  1285.  hashTablek= hashTable+DhashTable;
  1286.  posTable= new char[maxPos*posSize2];
  1287.  UposTable= posTable+DHDR;
  1288.  posTablek= UposTable + maxPos*posSize2;
  1289.  UfoundPos=UfoundPosD=0;
  1290.  testing=0;
  1291.  finalDone=0;
  1292.  if(!posTable){
  1293.    noMem();
  1294.    movedObj=0;
  1295.    finalPos=0;
  1296.    return 1;
  1297.  }
  1298.  memset(hashTable,0,DhashTable*sizeof(*hashTable));
  1299.  
  1300.  //poΦßteΦnφ a koncovß pozice
  1301.  UfinalPos= finalPos= new char[Nstore*DXY];
  1302.  p1=distBuf1;
  1303.  p2=distBuf2;
  1304.  UstartPos= UposTable;
  1305.  wrXY(UstartPos, mover->i);
  1306.  pf=fin2p;
  1307.  for(p=board; p<boardk; p++){
  1308.    p->finalDist=MAXDIST;
  1309.    if(p->store){
  1310.      p->finalDist=0;
  1311.      *p1++=p;
  1312.      *p2++=p;
  1313.      *pf++=p;
  1314.      wrXY(UfinalPos,p->i);
  1315.    }
  1316.    if(p->obj==BM_OBJECT){
  1317.      wrXY(UstartPos,p->i);
  1318.    }
  1319.    if(p->i!=-1){
  1320.      i2p[p->i]=p;
  1321.      p->finalDists= UfinA;       
  1322.      UfinA += Nstore;
  1323.      p->direct=-1;
  1324.      for(j=0; j<4; j++){
  1325.        if((prvP(p,j)->cont[j]&-2)==0 &&   
  1326.           p->cont[j]==-1 && !p->store &&
  1327.           (nxtP(p,j^2)->obj==BM_WALL || nxtP(p,j^3)->obj==BM_WALL)){
  1328.          p->cont[j]=2;
  1329.        }
  1330.        if(p->cont[j]==1 &&
  1331.           (p->store || (prvP(p,j)->cont[j]&-2))){
  1332.          p->cont[j]=0;
  1333.        }
  1334.      }
  1335.    }
  1336.  }
  1337.  assert(UfinA==finalDistA+Nground*Nstore);
  1338.  //po°adφ koncov²ch polφΦek
  1339.  *p1=*p2=0;
  1340.  ps=distBuf2;
  1341.  for(d=Nstore; *ps && d>=0; d--){
  1342.    for(p1=ps; *p1; p1++){
  1343.      for(i=0; i<4; i++){
  1344.        pn= nxtP(*p1,i);
  1345.        pnn= nxtP(pn,i);
  1346.        if(pn->obj!=BM_WALL && pnn->obj!=BM_WALL &&
  1347.           pn->finalDist>d && pnn->finalDist>d){
  1348.          (*p1)->finalDist=d;
  1349.          *p1=*ps++;
  1350.          break;
  1351.        }
  1352.      }
  1353.    }
  1354.  }
  1355.  //v²poΦet finalDist
  1356.  for(d=(Nstore+1)|1; ; d++){
  1357.    if(d&1) p1=distBuf1,p2=distBuf2;
  1358.    else p1=distBuf2,p2=distBuf1;
  1359.    if(!*p1) break;
  1360.    for( ; *p1; p1++){
  1361.      for(i=0; i<4; i++){
  1362.        pn= nxtP(*p1,i);
  1363.        pnn= nxtP(pn,i);
  1364.        if(pn->finalDist>=MAXDIST && pn->obj!=BM_WALL && pnn->obj!=BM_WALL
  1365.          && pn->obj!=BM_BACKGROUND){
  1366.          pn->finalDist=d;
  1367.          *p2++=pn;
  1368.        }
  1369.      }
  1370.    }
  1371.    *p2=0;
  1372.  }
  1373.  //vypoΦti finalDists[j]
  1374.  for(p1=fin2p; p1<fin2p+Nstore; p1++){
  1375.    (*p1)->finalDist=0;
  1376.  }
  1377.  finRadius= new int[Nstore];
  1378.  for(k=Nstore; k; ){
  1379.    for(j=0; j<k; j++){
  1380.      for(p1=i2p; p1<i2p+Nground; p1++){
  1381.        (*p1)->finalDists[j]=MAXDIST;
  1382.      }
  1383.      p=fin2p[j];
  1384.      distBuf1[0]=p;
  1385.      distBuf1[1]=0;
  1386.      p->finalDists[j]=0;
  1387.      for(d=(Nstore+1)|1; ; d++){
  1388.        if(d&1) p1=distBuf1,p2=distBuf2;
  1389.        else p1=distBuf2,p2=distBuf1;
  1390.        if(!*p1) break;
  1391.        for( ; *p1; p1++){
  1392.          for(i=0; i<4; i++){
  1393.            pn= nxtP(*p1,i);
  1394.            pnn= nxtP(pn,i);
  1395.            if(pn->obj!=BM_WALL  && pn->obj!=BM_BACKGROUND &&
  1396.               pn->finalDists[j]>=MAXDIST &&
  1397.               pnn->obj!=BM_WALL &&
  1398.               pn->finalDist>=k && pnn->finalDist>=k){
  1399.              pn->finalDists[j]=d;
  1400.              *p2++=pn;
  1401.            }
  1402.          }
  1403.        }
  1404.        *p2=0;
  1405.      }
  1406.      finRadius[j]=d;
  1407.    }
  1408.    m=MAXDIST;
  1409.    jm=0;
  1410.    for(j=0; j<k; j++){
  1411.      if(finRadius[j]<=m && finRadius[j] > Nstore+5 &&
  1412.        (finRadius[j]<m || k==Nstore ||
  1413.         fin2p[k]->finalDists[j] < fin2p[k]->finalDists[jm])){
  1414.        m=finRadius[j];
  1415.        jm=j;
  1416.      }
  1417.    }                   
  1418.    k--;
  1419.    p=fin2p[jm];
  1420.    fin2p[jm]=fin2p[k];
  1421.    fin2p[k]=p;
  1422.    p->finalDist=k;
  1423.    for(p1=i2p; p1<i2p+Nground; p1++){
  1424.      p=*p1;
  1425.      w= p->finalDists[k];
  1426.      p->finalDists[k]= p->finalDists[jm];
  1427.      p->finalDists[jm]= w;
  1428.      if(p->finalDist<k) p->finalDists[k]=0;
  1429.    }
  1430.  }
  1431.  fin2p[Nstore]= board;
  1432.  delete[] finRadius;
  1433.  assert(testPos(UposTable));
  1434.  if(!memcmp(finalPos,UposTable+DXY,posSize1-DXY)){
  1435.    UfoundPos=UfoundPosD=UposTable;
  1436.  }
  1437.  movedObj= new Move[Nobj*4*maxPos];
  1438.  if(!movedObj){
  1439.    noMem();
  1440.    return 1;
  1441.  }
  1442.  return 0;
  1443. }
  1444. //-------------------------------------------------------------------
  1445. void thinkDestroy()
  1446. {
  1447.  delete[] movedObj;
  1448.  delete[] finalPos;
  1449.  delete[] posTable;
  1450.  delete[] hashTable;
  1451.  delete[] fin2p;
  1452.  delete[] i2p;
  1453.  delete[] finalDistA;
  1454.  delete[] firstMove; firstMove=0;
  1455. }
  1456. //-------------------------------------------------------------------
  1457. void gener()
  1458. {
  1459.  Pchar *u,v,curPos,newPos;
  1460.  PHdr4 curPosHdr,newPosHdr;
  1461.  PMove Umoves,Umoves1;
  1462.  Psquare *pp;
  1463.  
  1464.  algorithm=3;
  1465.  if(thinkInit()){
  1466.    thinkDestroy();
  1467.    return;
  1468.  }
  1469.  curPos= UposTable;
  1470.  curPosHdr=HDR4(curPos);
  1471.  curPosHdr->mov=curPosHdr->pus=0;
  1472.  curPosHdr->movesBeg= movedObj;
  1473.  curPosHdr->movesEnd= Umoves= findObjectsR(movedObj);
  1474.  for(v=curPos+DXY; v<curPos+posSize1; v+=DXY){
  1475.    assert(i2p[rdXY(v)]->obj==BM_OBJECT);
  1476.    i2p[rdXY(v)]->obj=BM_GROUND;
  1477.  }
  1478.  UposTable+=posSize2;
  1479.  for( ;curPos<UposTable; curPos+=posSize2){
  1480.    curPosHdr= HDR4(curPos);
  1481.    //vytvo° aktußlnφ pozici
  1482.    for(v=curPos+DXY; v<curPos+posSize1; v+=DXY){
  1483.      assert(i2p[rdXY(v)]->obj==BM_GROUND);
  1484.      i2p[rdXY(v)]->obj=BM_OBJECT;
  1485.    }
  1486.    for(Umoves1=curPosHdr->movesBeg; Umoves1<curPosHdr->movesEnd; Umoves1++){
  1487.      Move &curMove= *Umoves1;
  1488.      newPos=UposTable;
  1489.      if(newPos==posTablek) break;
  1490.      newPosHdr=HDR4(newPos);
  1491.      //prove∩ tah
  1492.      assert(testPos(curPos));
  1493.      assert(curMove.next->obj==BM_GROUND);
  1494.      assert(curMove.obj->obj==BM_OBJECT);
  1495.      curMove.next->obj= BM_OBJECT;
  1496.      curMove.obj->obj= BM_GROUND;
  1497.      //vytvo° novou pozici
  1498.      mover= prvP(curMove.next,curMove.direct);
  1499.      //najdi vÜechny mo₧nΘ p°esuny v novΘ pozici
  1500.      newPosHdr->movesEnd= findObjectsR(Umoves);
  1501.      if(newPosHdr->movesEnd>Umoves){
  1502.        makeMove(newPos,curPos,curMove);
  1503.        newPosHdr->mov= (short)(curPosHdr->mov + curMove.dist);
  1504.        newPosHdr->pus= (short)(curPosHdr->pus + 1);
  1505.        //hrßΦe dej do levΘho hornφho rohu
  1506.        for(pp=i2p; (*pp)->distId!=distId; pp++) ;
  1507.        wrXY0(newPos,(*pp)->i);
  1508.        //vypoΦti hashovacφ funkci
  1509.        u=hash(newPos);
  1510.        for(;;){
  1511.          if(!*u){
  1512.            //p°idej novou pozici do tabulky
  1513.            *u=newPos;
  1514.            UposTable+=posSize2;
  1515.            newPosHdr->movesBeg= Umoves;
  1516.            Umoves= newPosHdr->movesEnd;
  1517.            #ifdef DEBUG
  1518.              repaint();
  1519.            #endif
  1520.            break;
  1521.          }
  1522.          if(!memcmp(*u,newPos,posSize1)){
  1523.            //pozice byla v tabulce nalezena
  1524.            break;
  1525.          }
  1526.          u++;
  1527.          if(u==hashTablek) u=hashTable;
  1528.        }
  1529.      }
  1530.      //vra¥ tah zp∞t
  1531.      curMove.next->obj= BM_GROUND;
  1532.      curMove.obj->obj= BM_OBJECT;
  1533.    }
  1534.    //sma₧ vÜechny objekty
  1535.    for(v=curPos+DXY; v<curPos+posSize1; v+=DXY){
  1536.      assert(i2p[rdXY(v)]->obj==BM_OBJECT);
  1537.      i2p[rdXY(v)]->obj=BM_GROUND;
  1538.    }
  1539.  }
  1540.  //nastav poslednφ nalezenou pozici
  1541.  curPos=UposTable-posSize2;
  1542.  curPosHdr=HDR4(curPos);
  1543.  mover= i2p[rdXY(curPos)];
  1544.  for(v=curPos+DXY; v<curPos+posSize1; v+=DXY){
  1545.    i2p[rdXY(v)]->obj=BM_OBJECT;
  1546.  }
  1547.  repaint();
  1548.  msg("%d-%d\n%d", curPosHdr->mov, curPosHdr->pus,
  1549.    (UposTable-posTable)/posSize2);
  1550.  thinkDestroy();
  1551.  edUndo=edRec; edRedo=0;
  1552. }
  1553. //-------------------------------------------------------------------
  1554. //p°emφsti se ze src na dest
  1555. void wrSolPath(Psquare src, Psquare dest)
  1556. {
  1557.  Psquare p,pn;
  1558.  int i;
  1559.  
  1560.  if(!src) return;
  1561.  findDist(dest,src);
  1562.  assert(src->distId==distId);
  1563.  for(p=src; p!=dest; p=pn){
  1564.    for(i=0; ; i++){
  1565.      pn=nxtP(p,i);
  1566.      if(pn->dist==p->dist-1) break;
  1567.    }
  1568.    *UfoundSol++= (char) (i+'0');
  1569.  }
  1570. }
  1571. //-------------------------------------------------------------------
  1572. Pchar getParent(Pchar pos)
  1573. {
  1574.  switch(algorithm){
  1575.   case 0:
  1576.    return HDR2(pos)->parent;
  1577.   case 1:
  1578.    return HDR3(pos)->parent;
  1579.   case 2:
  1580.    return HDR1(pos)->parent;
  1581.  }
  1582.  return 0;
  1583. }
  1584. //-------------------------------------------------------------------
  1585. void wrSol()
  1586. {
  1587.  Pchar u,prv,v,v1,v2,foundSol;
  1588.  Psquare p,pn,moverS=0;               
  1589.  int d,direct,dual;
  1590.  
  1591.  //zapiÜ tahy vzniklΘ smazßnφm slep²ch uliΦek
  1592.  logPos=logbuf;
  1593.  for(u=firstMove; u<UfirstMove; u++){
  1594.    wrLog(*u);
  1595.  }
  1596.  //alokuj buffer pro v²sledek
  1597.  switch(algorithm){
  1598.   case 0:
  1599.    d=HDR2(UfoundPos)->eval;
  1600.   break;
  1601.   case 1:
  1602.    d=HDR3(UfoundPos)->mov+HDR3(UfoundPosD)->mov+Nground;
  1603.   break;
  1604.   case 2:
  1605.    d=HDR1(UfoundPos)->eval+HDR1(UfoundPosD)->eval+Nground;
  1606.   break;
  1607.  }
  1608.  foundSol= new char[d+1];
  1609.  
  1610.  for(dual=0; dual<2; dual++){
  1611.    UfoundSol=foundSol;
  1612.    //sma₧ objekty
  1613.    for(p=board; p<boardk; p++){
  1614.      if(p->obj==BM_OBJECT) p->obj=BM_GROUND;
  1615.    }
  1616.    //nastav pozici
  1617.    u= dual ? UfoundPosD:UfoundPos;
  1618.    if(!u) break;
  1619.    for(v=u+DXY; v<u+posSize1; v+=DXY){
  1620.      i2p[rdXY(v)]->obj=BM_OBJECT;
  1621.    }
  1622.    mover=0;
  1623.    if(dual) mover=moverS;
  1624.  
  1625.    //projdi pozice sm∞rem k poΦßteΦnφ nebo koncovΘ
  1626.    for(; (prv=getParent(u))!=0; u=prv){
  1627.      //zjisti sm∞r p°esunu mezi pozicemi prv, u
  1628.      for(v1=prv+DXY,v2=u+DXY; rdXY(v1)==rdXY(v2); v1+=DXY,v2+=DXY) ;
  1629.      d= rdXY(v2)-rdXY(v1);
  1630.      if(d>0){
  1631.        if(d!=1 || v1+DXY<prv+posSize1 && rdXY(v1+DXY)==rdXY(v2)){
  1632.          direct=2;
  1633.        }else{
  1634.          direct=0;
  1635.        }
  1636.        p=i2p[rdXY(v1)];
  1637.        pn=prvP(p,direct);
  1638.        if(pn->obj!=BM_OBJECT){
  1639.          assert(direct==0 && pn->obj==BM_WALL);
  1640.          pn=prvP(p,direct=2);
  1641.        }
  1642.      }else{
  1643.        if(d!=-1 || v2+DXY<u+posSize1 && rdXY(v1)==rdXY(v2+DXY)){
  1644.          direct=3;
  1645.        }else{
  1646.          direct=1;
  1647.        }
  1648.        pn=i2p[rdXY(v2)];
  1649.        p=nxtP(pn,direct);
  1650.        if(p->obj!=BM_GROUND){
  1651.          assert(direct==1);
  1652.          p=nxtP(pn,direct=3);
  1653.        }
  1654.      }
  1655.      //p°emφsti se k objektu
  1656.      wrSolPath(mover, dual ? prvP(pn,direct) : p);
  1657.      if(u==UfoundPos) moverS=p;
  1658.      //prove∩ p°esun z pn na p
  1659.      assert(pn->obj==BM_OBJECT);
  1660.      assert(p->obj==BM_GROUND);
  1661.      pn->obj=BM_GROUND;
  1662.      p->obj=BM_OBJECT;
  1663.      mover= dual ? pn : nxtP(p,direct);
  1664.      *UfoundSol++= (char) (direct+'4');
  1665.    }
  1666.    if(!dual){
  1667.      wrSolPath(mover, i2p[rdXY(posTable+DHDR)]);
  1668.      //prvnφ polovina °eÜenφ - obrßcen∞
  1669.      for(u=UfoundSol-1; u>=foundSol; u--){
  1670.        wrLog(char(*u^1));
  1671.      }
  1672.      if(algorithm==2){
  1673.        HDR1(UfoundPos)->parent=UfoundPosD;
  1674.        UfoundPosD=UfoundPos;
  1675.      }
  1676.    }else{
  1677.      //druhß polovina °eÜenφ
  1678.      for(u=foundSol; u<UfoundSol; u++){
  1679.        wrLog(*u);
  1680.      }
  1681.    }
  1682.  }
  1683.  delete[] foundSol;
  1684.  *logPos=0;
  1685.  logPos=0;
  1686. }
  1687. //-------------------------------------------------------------------
  1688. int findSolution(int alg)
  1689. {
  1690.  int k;
  1691.  DWORD time= GetTickCount();
  1692.  
  1693.  algorithm=alg;
  1694.  delBlind();
  1695.  if(thinkInit()){
  1696.    thinkDestroy();
  1697.    return -4;
  1698.  }
  1699.  if(Nobj!=Nstore || !Nobj) return -3;
  1700.  switch(algorithm){
  1701.   case 0:
  1702.    depthSearch();
  1703.   break;
  1704.   case 1:
  1705.    breadthSearch();
  1706.   break;           
  1707.   case 2:
  1708.    dijkstra();
  1709.   break;
  1710.  }
  1711.  assert(UposTable<=posTablek);
  1712.  if(UfoundPos){
  1713.    //zapiÜ a "zkomprimuj" °eÜenφ
  1714.    wrSol();
  1715.  
  1716.    ///assert(algorithm!=2 || mov+pus==HDR1(UfoundPos)->eval);
  1717.    //if(algorithm==1) msg("%d-%d, %d-%d",HDR3(UfoundPos)->mov,HDR3(UfoundPos)->pus,HDR3(UfoundPosD)->mov,HDR3(UfoundPosD)->pus);
  1718.  }
  1719.  thinkDestroy();
  1720.  time=GetTickCount()-time;
  1721.  if(UfoundPos){
  1722.    loadSolution(level, logbuf);
  1723.    assert(!movError);
  1724.    //zapsßnφ °eÜenφ do databßze
  1725.    finish();
  1726.    saveUser();
  1727.    saveData();
  1728.    status();
  1729.    if(gratulOn){
  1730.      k= int(((char*)UposTable-(char*)posTable)/posSize2);
  1731.      msg("Solution: %d-%d\nTime: %d ms\n\nPositions: %d, %d",
  1732.      moves,pushes, time, k, maxPos - int(((char*)posTablek-(char*)UposTable)/posSize2) - k);
  1733.    }
  1734.    return moves+pushes;
  1735.  }else{
  1736.    resetLevel();
  1737.  }
  1738.  if(UposTable==posTablek){
  1739.    if(gratulOn){
  1740.      k= int((char*)UposTable-(char*)posTable)/posSize2;
  1741.      msg("Timeout: %d ms\n\nPositions: %u, %u",
  1742.        time, k, maxPos - k);
  1743.    }
  1744.    return -1;
  1745.  }
  1746.  msg("Unsolvable");
  1747.  return -2;
  1748. }
  1749. //-------------------------------------------------------------------
  1750.  
  1751.